#include <iostream>
#include <vector>
#include <algorithm>

struct ListNode
{
    int val;
    ListNode * next;
    ListNode() : val(0), next(nullptr)
    {}
    ListNode(int val) : val(val), next(nullptr)
    {}
    ListNode(int val, ListNode * next) : val(val), next(next)
    {}
};

class Solution 
{
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) 
    {
        int lenA = 0;
        int lenB = 0;
        ListNode * _dummyHeadA = new ListNode(0, headA);
        ListNode * _dummyHeadB = new ListNode(0, headB);
        ListNode * curA = headA;
        ListNode * curB = headB;
        while (curA != nullptr)
        {
            lenA++;
            curA = curA->next;
        }
        while (curB != nullptr)
        {
            lenB++;
            curB = curB->next;
        }
        if(lenB > lenA)
        {
            std::swap(lenA, lenB);
            std::swap(_dummyHeadA, _dummyHeadB);
        }
        curA = _dummyHeadA;
        curB = _dummyHeadB;
        int gap = lenA - lenB;
        bool flag = false;

        while (gap != 0)
        {
            curA = curA->next;
            gap--;
        }

        while (curA != nullptr)
        {
            if(curA == curB)
            {
                flag = true;
                break;
            }
            curA = curA->next;
            curB = curB->next;
        }
        return curA;
    }
};


// 辅助函数：根据数组创建链表
ListNode* createList(const std::vector<int>& vals) {
    if (vals.empty()) return nullptr;
    ListNode* dummy = new ListNode(0);
    ListNode* cur = dummy;
    for (int v : vals) {
        cur->next = new ListNode(v);
        cur = cur->next;
    }
    ListNode* head = dummy->next;
    delete dummy;
    return head;
}

// 辅助函数：打印链表
void printList(ListNode* head) {
    ListNode* cur = head;
    while (cur) {
        std::cout << cur->val;
        if (cur->next) std::cout << "->";
        cur = cur->next;
    }
    std::cout << std::endl;
}

int main() {
    Solution sol;

    // 测试用例1：两个链表有交点
    // A: 1->2->3
    //                \
    //                 6->7
    //                /
    // B:      4->5
    ListNode* common = new ListNode(6, new ListNode(7));
    ListNode* headA = new ListNode(1, new ListNode(2, new ListNode(3, common)));
    ListNode* headB = new ListNode(4, new ListNode(5, common));

    std::cout << "链表A: ";
    printList(headA);
    std::cout << "链表B: ";
    printList(headB);

    ListNode* intersection = sol.getIntersectionNode(headA, headB);
    if (intersection) {
        std::cout << "交点值: " << intersection->val << std::endl;
    } else {
        std::cout << "无交点" << std::endl;
    }
    std::cout << std::endl;

    // 测试用例2：两个链表无交点
    ListNode* headC = createList({1, 2, 3});
    ListNode* headD = createList({4, 5, 6});
    std::cout << "链表C: ";
    printList(headC);
    std::cout << "链表D: ";
    printList(headD);

    ListNode* intersection2 = sol.getIntersectionNode(headC, headD);
    if (intersection2) {
        std::cout << "交点值: " << intersection2->val << std::endl;
    } else {
        std::cout << "无交点" << std::endl;
    }
    std::cout << std::endl;

    // 测试用例3：一个链表为空
    ListNode* headE = nullptr;
    ListNode* headF = createList({7, 8, 9});
    std::cout << "链表E: ";
    printList(headE);
    std::cout << "链表F: ";
    printList(headF);

    ListNode* intersection3 = sol.getIntersectionNode(headE, headF);
    if (intersection3) {
        std::cout << "交点值: " << intersection3->val << std::endl;
    } else {
        std::cout << "无交点" << std::endl;
    }
    std::cout << std::endl;

    // 测试用例4：两个链表都是空
    ListNode* headG = nullptr;
    ListNode* headH = nullptr;
    std::cout << "链表G: ";
    printList(headG);
    std::cout << "链表H: ";
    printList(headH);

    ListNode* intersection4 = sol.getIntersectionNode(headG, headH);
    if (intersection4) {
        std::cout << "交点值: " << intersection4->val << std::endl;
    } else {
        std::cout << "无交点" << std::endl;
    }
    std::cout << std::endl;

    return 0;
}